import java.util.*;

public class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder ret = new StringBuilder();
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        while (!que.isEmpty()) {
            TreeNode ctop = que.peek();
            que.remove();
            if (ctop == null) ret.append("null,");
            else {
                ret.append(ctop.val);
                ret.append(",");
                que.add(ctop.left);
                que.add(ctop.right);
            }
        }
        return ret.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] _data = data.split(",");
        List<Integer> sdata = new LinkedList<>();
        for (String d : _data) {
            if (d.equals("null")) sdata.add(null);
            else sdata.add(Integer.parseInt(d));
        }
        Integer rootVal = sdata.get(0);
        if (rootVal == null) return null;
        TreeNode root = new TreeNode(rootVal);
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        int i = 1;
        while (!que.isEmpty() && i < sdata.size() - 1) {
            TreeNode ctop = que.peek();
            que.remove();
            Integer left = sdata.get(i);
            Integer right = sdata.get(i + 1);
            if (left == null) ctop.left = null;
            else {
                ctop.left = new TreeNode(left);
                que.add(ctop.left);
            }
            if (right == null) ctop.right = null;
            else {
                ctop.right = new TreeNode(right);
                que.add(ctop.right);
            }
            i += 2;
        }
        return root;
    }
}